Communication in AHN may take place directly between two mobile nodes, if they are within an appropriate range of one another. More common is the case of multi-hop routing, in which nodes lying between the source node S and destination node D serve as routers, conveying data from source to destination via multiple hops. It is technically challenging to find such multi-hop paths, since the topology of the AHN is constantly changing due to the motion of the nodes. Thus it is, in general, challenging to route messages between nodes in an AHN.
It should be noted that routing from a mobile node to a gateway node G (which is usually fixed in place) is also of significant interest. The gateway node then gives access from the mobile AHN to a fixed network. Node-gateway routing can in principle include the multi-hop case, in which (again) intermediate mobile nodes serve as routers passing data to and from the gateway.
The phrase “multi-hop routing in an ad-hoc network” can be used to apply to either of these two cases (mobile mobile and mobile gateway).
The problem is to find good paths between pairs of nodes in an AHN that wish to communicate. There are various criteria for “good” paths. The path must be feasible (that is, it must not be based on outdated topology information, which uses links that no longer exist). The path should also be as short as possible to minimize the use of bandwidth for relaying; and it should avoid congested areas which give rise to undesirable delay in the passing of data.
Depending on the circumstances and the application, there can be other criteria for goodness of a path. The present invention is useful for any criteria of goodness, as long as these criteria can be measured in the course of the transmission of the data along the path. The criteria mentioned above (existence, length, and delay of the path) are all measurable.
Finding good paths is a readily soluble problem for a fixed, static network. When the network topology is time dependent, entirely new problems arise. For a realistic and practical span of node mobility and wireless communications range, the network topology of an AHN can change more rapidly than traditional methods, used for static networks, can follow. Hence new path-finding (routing) methods must be found for such dynamic networks.
Routing in AHN has been studied intensively over the last 10-15 years. The number of proposed routing protocols for an AHN is very large, and it is not practical to try to list them all here.
Some overviews of ad-hoc routing protocols include the following:
S. Ramanathan and M. Steenerup, “A survey of routing techniques for mobile communications networks”, Mobile networks and Applications, vol. 1 no. 2, p. 89, 1996.
J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu, and J. Jetcheva, “A performance comparison of multi-hop wireless ad hoc network routing protocols”, Proc. MobiCom '98, Dallas, Tex., USA, 1998.
E. M. Royer and C.-K. Toh, “A review of current routing protocols for ad hoc mobile wireless networks”, IEEE Personal Communications, April 1999, p. 46.
An electronic overview by Christian Tschudin of Uppsala University is at:
http://www.docs.uu.se/tschudin/lect/2Q002001/dn2/slides/ad hoc-4up. ndf.
There is also a working group of the Internet Engineering Task Force (IETF), which is dedicated to Mobile Ad-hoc Networks or MANETs. See:
http://www.ietf.org/html.charters/manet-charter.html.
Further, stochastic routing has been proposed for routing in fixed (but dynamic) networks in numerous research papers. There is one research paper describing a specific stochastic routing scheme for ad-hoc networks: P. Gupta and P. R. Kumar, “A system and traffic dependent adaptive routing algorithm for ad hoc networks, Proceedings of the 36th IEEE Conference on Decision and Control, pp. 2375-2380, San Diego, December 1997.
Stochastic routing is a form of multipath routing. In multipath routing, nodes maintain routing tables (RTs) with multiple choices of path for each possible destination. For dynamic networks it is advantageous to maintain multiple paths, as it allows for rapid change of path in case the first choice of path fails. Stochastic routing entails the maintenance of information about multiple paths, and also that the choice among multiple paths be made probabilistically rather than deterministically. Thus stochastic routing necessarily involves the following elements: each node S. viewed as a source of data, maintains an RT for every possible destination D. Each such RT has an entry for every neighbor k of S with a probability p(k, D). Thus, whenever data are to be sent from S to D, neighbor k is chosen with probability p(k,D).
Most ad-hoc routing protocols attempt to find a full path from a first node S to a second node D before sending data. There are two broad categories for protocols doing this:
Proactive protocols: These protocols attempt to maintain a complete routing solution for the entire network at all times. In this sense, they are like those approaches used for routing on a static network, although they are of course adapted to better deal with the dynamic nature of the AHN. These protocols are also known as “table-driven,” since they attempt to maintain information amounting to a complete set of routing tables for all S-D pairs.
Reactive protocols: These protocols attempt to find paths from S to D only when the source S needs to send data to destination D. They are also known as “source-initiated” or “on-demand” protocols. A recent evaluation of two of the most prominent on-demand protocols is: C. E. Perkins, E. M. Royer, S. R. Das, and M. K. Marina, “Performance comparison of two on-demand routing protocols for ad-hoc networks”, IEEE Personal Communications, February 2001, p. 16.
There are ad-hoc routing schemes that do not need to find a full path before sending data. Such schemes use one or both of the following mechanisms:
Hierarchical protocols: the network is broken up into clusters. Routing within a cluster is done by any of the above-mentioned non-hierarchical methods. However, routing to a node outside S's cluster is done by sending the data to a designated gateway node. (Here the gateway is to another cluster, not to a fixed net; the gateway nodes are also mobile nodes.) Data are then passed from cluster to cluster via the gateway nodes that must solve the intercluster routing problem until it reaches the cluster in which D lies. Then the data are routed to D using the intracluster protocol. Such hierarchical routing mimics that used for the static Internet.
Location-aided protocols: If S knows its own geographic location, as well as that of D, it can send data in the direction of D without knowing a complete path to D. The challenge is then to maintain up-to-date information on the location of possible destination nodes, which are mobile. If the destination node is a fixed gateway node G (giving access to a fixed net), then this challenge is trivial and one needs only to equip each mobile node with positioning technology.
There is probably no unique best solution to the problem of multi-hop routing on an ad-hoc net. Such networks can vary widely in the mobility of the nodes and in the pattern and volume of internode traffic. Each different type of routing scheme has its own weaknesses as described below.
Proactive protocols: Such protocols obviously work best when the network topology is slowly varying. By the same token, when the network is too dynamic (e.g., because the nodes are too mobile) these protocols swamp the network with overhead messages, seeking to hold the full set of routing tables updated in the face of too much time variation of the network. That is, these protocols fail when the network topology changes too often—typically because the node mobility is too high, and/or the network is too large. In short, the principle problem with proactive protocols is the large routing overhead incurred for dynamic networks.
Reactive protocols: These protocols seek routes only when they are needed, thus reducing their routing overhead with respect to proactive protocols. That is, their routing overhead grows with network traffic rather than with network transience. These schemes can thus work well for a highly dynamic network, as long as the traffic rate is not too high. For this reason they tend to be preferred over proactive protocols.
Reactive protocols fail when the rate at which paths must be found exceeds the rate at which they can be found. This occurs due to high traffic (which increases the former rate), high network transience (which increases the former rate and decreases the latter), or large network size (which decreases the latter rate). They are particularly vulnerable to the latter factor: if the network grows too large, then the time needed to find paths on demand can exceed the time for which the path is valid—at which point routing becomes impossible.
Of course, there is no AHN routing scheme which can handle an arbitrarily large network. However, the need to find an entire path in real time is a significant bottleneck for both of these classes of protocols-reactive and proactive.
Hierarchical protocols: These schemes avoid the need to find an entire path before sending data. However, they face problems similar to those faced by proactive schemes—that is, they fail for networks that are too large and/or too dynamic. The reason is that they must repeatedly solve a network-wide problem: the choice of how to cluster the nodes into a hierarchy, and how to route between the clusters. For some mobility patterns (say, when nodes tend naturally to move in clusters), the solutions to this global problem will not vary too rapidly. However, for the general AHN, with highly mobile nodes moving in an uncorrelated fashion, a hierarchical scheme will incur unacceptable overhead costs, particularly if the network is large.
Location-aided protocols: These protocols largely avoid the overhead problems of the above-mentioned types, as they simply need to know the location of their destination in order to send data. They then have two weaknesses. First, it can be difficult to obtain good enough information about the location of the destination. The source does not need exact knowledge of D's location, and so such schemes can work with partly-outdated information. Furthermore, regular communication with D serves to keep its location updated. Hence a problem arises only when nodes communicate in an irregular fashion (over time) with a number of different nodes, which are also far away geographically.
A second problem with location-aided routing schemes is that they naturally rely on “aiming” the data towards D. That is, the next hop is chosen to be that neighbor closest to D. The problem arises when data arrive at a node that cannot reach D directly and which also has no neighbor which is closer to D than it is itself. Such a node represents a “dead end” for this type of routing scheme, which thus must be augmented with some mechanism for routing around dead ends. Dead ends are most likely for AHNs with a low and/or very uneven density of nodes.
Finally (as noted above), note that routing to a fixed gateway node has only the second of these two problems since the location of the destination G is always known.